{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过列表生成式，我们可以直接创建一个列表。但是，受到内存限制，列表容量肯定是有限的。而且，创建一个包含100万个元素的列表，不仅占用很大的存储空间，如果我们仅仅需要访问前面几个元素，那后面绝大多数元素占用的空间都白白浪费了。\n",
    "\n",
    "所以，如果列表元素可以按照某种算法推算出来，那我们是否可以在循环的过程中不断推算出后续的元素呢？这样就不必创建完整的list，从而节省大量的空间。在Python中，这种一边循环一边计算的机制，称为生成器：generator。\n",
    "\n",
    "要创建一个generator，有很多种方法。第一种方法很简单，只要把一个列表生成式的[]改成()，就创建了一个generator："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = [x * x for x in range(10)]\n",
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object <genexpr> at 0x000001DB86E9F448>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = (x * x for x in range(10))\n",
    "g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 打印出generator的每一个元素呢\n",
    "# 如果要一个一个打印出来，可以通过next()函数获得generator的下一个返回值\n",
    "next(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "4\n",
      "9\n",
      "16\n",
      "25\n",
      "36\n",
      "49\n",
      "64\n",
      "81\n"
     ]
    }
   ],
   "source": [
    "# 使用for循环, generator也是可迭代对象\n",
    "g = (x * x for x in range(10))\n",
    "for n in g:\n",
    "    print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "generator非常强大。如果推算的算法比较复杂，用类似列表生成式的for循环无法实现的时候，还可以用函数来实现。\n",
    "\n",
    "比如，著名的斐波拉契数列（Fibonacci），除第一个和第二个数外，任意一个数都可由前两个数相加得到：\n",
    "\n",
    "1, 1, 2, 3, 5, 8, 13, 21, 34, ...\n",
    "\n",
    "斐波拉契数列用列表生成式写不出来，但是，用函数把它打印出来却很容易："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(max):\n",
    "    n, a, b = 0, 0, 1\n",
    "    while n < max:\n",
    "        print(b)\n",
    "        a, b = b, a + b # 相当于t = (b, a + b), a = t[0], b = t[1]\n",
    "        n = n + 1\n",
    "    return 'done'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "5\n",
      "8\n",
      "13\n",
      "21\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'done'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 上面的函数可以输出斐波那契数列的前N个数：\n",
    "fib(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的函数和generator仅一步之遥。要把fib函数变成generator，只需要把print(b)改为yield b就可以了："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(max):\n",
    "    n, a, b = 0, 0, 1\n",
    "    while n < max:\n",
    "        yield b\n",
    "        a, b = b, a + b\n",
    "        n = n + 1\n",
    "    return 'done'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这就是定义generator的另一种方法。如果一个函数定义中包含yield关键字，那么这个函数就不再是一个普通函数，而是一个generator："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object fib at 0x000001DB86E9FD48>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = fib(6)\n",
    "f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里，最难理解的就是generator和函数的执行流程不一样。函数是顺序执行，遇到return语句或者最后一行函数语句就返回。而变成generator的函数，在每次调用next()的时候执行，遇到yield语句返回，再次执行时从上次返回的yield语句处继续执行。\n",
    "\n",
    "举个简单的例子，定义一个generator，依次返回数字1，3，5："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def odd():\n",
    "    print('step 1')\n",
    "    yield 1\n",
    "    print('step 2')\n",
    "    yield(3)\n",
    "    print('step 3')\n",
    "    yield(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o = odd()\n",
    "next(o)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step 2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(o)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step 3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(o)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-16-ac94be31f4f2>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mo\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(o)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到，odd不是普通函数，而是generator，在执行过程中，遇到yield就中断，下次又继续执行。执行3次yield后，已经没有yield可以执行了，所以，第4次调用next(o)就报错。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 练习\n",
    "杨辉三角定义如下：\n",
    "          1\n",
    "         / \\\n",
    "         1  1\n",
    "        / \\ / \\\n",
    "        1  2  1\n",
    "       / \\ / \\ / \\\n",
    "      1   3   3   1\n",
    "      / \\ / \\ / \\ /  \\\n",
    "     1   4  6   4   1\n",
    "    / \\  / \\  / \\  / \\ / \\\n",
    "   1   5   10  10  5   1\n",
    "\n",
    "把每一行看做一个list，试写一个generator，不断输出下一行的list："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triangles():\n",
    "    l = [1]\n",
    "    while True:\n",
    "        yield l\n",
    "        l=[1] + [l[x] + l[x+1] for x in range (len(l)-1)] + [1]\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "[1, 1]\n",
      "[1, 2, 1]\n",
      "[1, 3, 3, 1]\n",
      "[1, 4, 6, 4, 1]\n",
      "[1, 5, 10, 10, 5, 1]\n",
      "[1, 6, 15, 20, 15, 6, 1]\n",
      "[1, 7, 21, 35, 35, 21, 7, 1]\n",
      "[1, 8, 28, 56, 70, 56, 28, 8, 1]\n",
      "[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]\n",
      "测试通过!\n"
     ]
    }
   ],
   "source": [
    "n = 0\n",
    "results = []\n",
    "for t in triangles():\n",
    "    results.append(t)\n",
    "    n = n + 1\n",
    "    if n == 10:\n",
    "        break\n",
    "\n",
    "for t in results:\n",
    "    print(t)\n",
    "\n",
    "if results == [\n",
    "    [1],\n",
    "    [1, 1],\n",
    "    [1, 2, 1],\n",
    "    [1, 3, 3, 1],\n",
    "    [1, 4, 6, 4, 1],\n",
    "    [1, 5, 10, 10, 5, 1],\n",
    "    [1, 6, 15, 20, 15, 6, 1],\n",
    "    [1, 7, 21, 35, 35, 21, 7, 1],\n",
    "    [1, 8, 28, 56, 70, 56, 28, 8, 1],\n",
    "    [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]\n",
    "]:\n",
    "    print('测试通过!')\n",
    "else:\n",
    "    print('测试失败!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
